import java.util.Arrays;

class Solution {
    public int[][] phone;
    public int mod;
    public int[][] memory;
    public int knightDialer(int n) {
        int ans=0;
        memory=new int[10][5005];
        for(int[] x:memory){
            Arrays.fill(x,-1);
        }
        //memory[i][j]中i表示数字号码，j表示以i结束，后面还有j个长度的数字
        phone= new int[][]{{1, 2, 3}, {4, 5, 6}, {7,8,9}, {-1,0,-1}};
        mod=1000000007;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                if(phone[i][j]!=-1){
                    ans=(ans+dfs(i,j,n-1))%mod;
                }
            }
        }
        return ans;
    }
    public int[] dx={-1,-2,-2,-1,1,2,2,1};
    public int[] dy={-2,-1,1,2,2,1,-1,-2};
    public int dfs(int a,int b,int k){
        if(memory[phone[a][b]][k]!=-1){
            return memory[phone[a][b]][k];
        }
        if(k==0){
            return 1;
        }
        int ans=0;
        for (int i = 0; i < 8; i++) {
            int x=a+dx[i];
            int y=b+dy[i];
            if(x>=0 && x<4 && y>=0 && y<3 && phone[x][y]!=-1){
                ans=(ans+dfs(x,y,k-1))%mod;
            }
        }
        memory[phone[a][b]][k]=ans;
        return ans;
    }
}